const treeList: ITreeItem[] = [
    {
        id: 1,
        name: "食品",
        children: [
            {
                id: 11,
                name: "面食",
                parent: 1,
                children: [
                    {
                        id: 111,
                        name: "热干面",
                        parent: 11,
                    },
                ],
            },
        ],
        parent: null,
    },
    {
        id: 2,
        name: "衣服",
        parent: null,
    },
];

export interface ITreeItem {
    id: number;
    name: string;
    parent?: null | number;
    children?: ITreeItem[];
    level?: number;
    [propName: string]: any;
}

type TreeList = ITreeItem[];

// 深度优先 遍历树状结构
export function treeForeachDeep(
    tree: ITreeItem[],
    func: (arg: ITreeItem) => void
) {
    tree.forEach((data) => {
        func(data);
        data.children && treeForeachDeep(data.children, func); // 遍历子树
    });
}

// treeForeachDeep(treeList, data => console.log(data.name))

const list: ITreeItem[] = [
    {
        id: 1,
        name: "食品",
        parent: null,
    },
    {
        id: 2,
        name: "衣服",
        parent: null,
    },
    {
        id: 11,
        name: "面食",
        parent: 1,
    },
    {
        id: 12,
        name: "米饭",
        parent: 1,
    },
    {
        id: 111,
        name: "热干面",
        parent: 11,
    },
    {
        id: 121,
        name: "白米饭",
        parent: 12,
    },
];

interface ITreeMap {
    [propName: string]: ITreeItem;
}

// 把一维的数组结构转换成树状结构
export function listToTree(list: ITreeItem[]) {
    let info = list.reduce(
        (map: ITreeMap, node) => ((map[node.id] = node), (node.children = []), map),
        {}
    ); // {1: {id:1, name: '食品',children: []}， 11： {id：11}}
    return list.filter((node) => {
        node.parent && info[node.parent] && info[node.parent].children!.push(node);
        return !node.parent;
    });
}

// 把树状结构转换成一维数组
// tree: 树状结构 ， result 返回一位数组， level 记录每个节点层级
export function treeToList(tree: ITreeItem[], result: ITreeItem[] = [], level: number = 0): ITreeItem[] {
    tree.forEach((node) => {
        result.push(node);
        node.level = level + 1;
        node.children && treeToList(node.children, result, level + 1);
    });
    return result;
}

console.log(listToTree(list));


// 筛选结果返回树状结构
// [1,2,3,4,5].filter((item) => item > 2 )
export function treeFilter(tree: ITreeItem[], func: (node: ITreeItem) => boolean): ITreeItem[] {
    // 使用map复制一下节点，避免修改到原树
    return tree
        .map((node) => ({ ...node }))
        .filter((node) => {
            node.children = node.children && treeFilter(node.children, func);
            return func(node) || (node.children && node.children.length);
        });
}

// 从树状结构中查找某个节点， 返回找到的节点的对象
// [{id:1}, {id:2}].find(item => item.id === 1 )
export function treeFind(tree: ITreeItem[], func: (node: ITreeItem) => boolean): ITreeItem | null {
    for (const data of tree) {
        if (func(data)) return data;
        if (data.children) {
            const res = treeFind(data.children, func);
            if (res) return res;
        }
    }
    return null;
}

// 从树状结构中查找某个节点， 返回节点的父级路径
export function treeFindPath(tree: ITreeItem[], func: (node: ITreeItem) => boolean, path: number[] = []): number[] {
    if (!tree) return [];
    for (const data of tree) {
        path.push(data.id);
        if (func(data)) return path;
        if (data.children) {
            const findChildren = treeFindPath(data.children, func, path);
            if (findChildren.length) return findChildren;
        }
        path.pop();
    }
    return [];
}